package lianxi;

import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;

public class Test {

	public static void main(String[] args) {
		test(11);
	}

	/**
	 * key是行
	 * 
	 * value 是每行的内容(List)
	 * 
	 * 需要使用TreeMap 因为需要保证有序,并且 key既然是行号,肯定是Integer类型,默认从小到大排序,咱们不需要进行排序,默认就行
	 * 
	 * @param n
	 */
	public static void test(int n) {
		Map<Integer, ArrayList<Integer>> datas = new TreeMap<Integer, ArrayList<Integer>>();

		// 行初始化循环,i表示行号
		for (int i = 1; i <= n; i++) {
			// 存储当前行的元素的集合
			ArrayList<Integer> nums = new ArrayList<Integer>();

			// 第一个元素设置为1
			nums.add(0, 1);

			// 存储上一行的数据的集合
			ArrayList<Integer> pr = null;
			if (i > 2) {
				// 如果 i大于2 说明不是前两行,因为前两行都是1
				// 所以我们从第三行开始获取上一行的数据
				// i是当前行,上一行就是 i-1
				pr = datas.get(i - 1);
			}
			// 初始化非首尾元素
			// 只有第三行才会有非首尾元素
			// 并且非首尾元素的 第一个下标是 1 最后一个下标是 i-2(i是行号,比如
			// i=4,就说明有4个元素,最后一个元素下标是-1,所以非首尾的最后一个元素就是i-2)
			// 这里的j 表示 i 行的 某一列
			for (int j = 1; j <= i - 2; j++) {
				// 能到这里 最起码也是第三行
				// i 行 j 列 = (i-1 行 j-1列) + (i-1行 j列)
				// i-1行 我们取出来赋值给 pr 了
				// 所以 i行j列 = (pr的 j-1列) + (pr的 j 列)

				// nums 就是 i 行的 数据集合
				nums.add(j, pr.get(j - 1) + pr.get(j));
			}

			// 最后一个元素设置为1
			// 第一行 只有一个元素,设置了首元素,就不需要再设置尾元素了
			// 设置尾元素必须在最后设置,要么中间还没有数据,是不能直接往后放数据的
			if (i > 1) {
				nums.add(i - 1, 1);
			}

			// 把当前行的数据添加到map中
			datas.put(i, nums);
		}

		// 遍历展示
		for (ArrayList<Integer> data : datas.values()) {
			// 输出一个集合的时候,会自动调用每个元素自身的toString()方法
			// 因为我们集合中保存的是Integer,并且Integer中覆写了toString()
			// 所以这里输出的是值 而不是内存地址
			System.out.println(data.size());
		}
	}
}
